package com.heima.leetcode.datastructure.binarytree;

import java.util.LinkedList;

/**
 * <strong>求二叉树的最小深度，和深度有关的，理应考虑到叶子节点 111</strong>
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/8 18:12
 */
public class MinDepth {

    /**
     * <h3>方法一：递归实现，结合代码，可分析与后序遍历逻辑一致</h3>
     * @param root 当前树的根节点
     * @return 树的最小深度
     */
    public static int minDepth1(TreeNode root){
        // 递归结束条件：当前树为空
        if (root == null){
            return 0;
        }
        // 计算出左子树的深度和右子树的深度
        int leftDepth = minDepth1(root.left);
        int rightDepth = minDepth1(root.right);
        // 如果左子树的深度为0，说明左子树没有节点，不应该纳入比较范围
        if (leftDepth == 0){
            return 1 + rightDepth; // return说明是要结束当前树的计算，不要忘了加一
        }
        // 如果右子树的深度为0，说明右子树没有节点，不应该纳入比较范围
        if (rightDepth == 0){
            return 1 + leftDepth;
        }
        // 返回当前树的深度
        return 1 + Math.min(leftDepth,rightDepth);
    }

    /**
     * <h3>方法二：迭代实现，也就是非递归遍历，思路：计算根节点到叶子节点的距离</h3>
     * @param root 树的根节点
     * @return 树的最小深度
     */
    public static int minDepth2(TreeNode root){
        if (root == null){
            return 0;
        }
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode curr = root;
        TreeNode lastPop = null;
        int depth = 0;
        while (curr != null || !stack.isEmpty()){
            if (curr != null){
                stack.push(curr);
                curr = curr.left;
            }else {
                TreeNode last = stack.peek();
                if (last.right == null){
                    if (last.left == null && (depth == 0 || stack.size() < depth)){ // 限制last为叶子节点
                        depth = stack.size();
                    }
                    lastPop = stack.pop();
                }else if (last.right == lastPop){
                    lastPop = stack.pop();
                }else {
                    curr = last.right;
                }
            }
        }
        return depth;
    }

    /**
     * <h3>方法三：层序遍历法，层序遍历时，应找出第一个出现的叶子节点，该叶子节点所处的层就是最小深度</h3>
     * @param root 树的根节点
     * @return 树的最小深度
     */
    @SuppressWarnings("all")
    public static int minDepth3(TreeNode root){
        if (root == null){
            return 0;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int level = 0;
        while (!queue.isEmpty()){
            int size = queue.size();
            // 一轮for循环处理一层
            for (int i = 0; i < size; i++){
                TreeNode node = queue.poll();
                if (node.left != null){
                    queue.offer(node.left);
                }
                if (node.right != null){
                    queue.offer(node.right);
                }
                if (node.left == null && node.right == null){
                    return ++level; // 找出第一个出现的叶子节点
                }
            }
            level++;
        }
        return level;
    }
}
